/*
 * Copyright (C) 2017 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.google.common.collect;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;

import java.util.Arrays;

import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * {@code ObjectCountLinkedHashMap} is a subclass of {@code ObjectCountHashMap} with insertion
 * iteration order, and uses arrays to store key objects and count values. Comparing to using a
 * traditional {@code LinkedHashMap} implementation which stores keys and count values as map
 * entries, {@code ObjectCountLinkedHashMap} minimizes object allocation and reduces memory
 * footprint.
 */
@GwtCompatible(serializable = true, emulated = true)
@ElementTypesAreNonnullByDefault
class ObjectCountLinkedHashMap<K extends @Nullable Object> extends ObjectCountHashMap<K>
{
    /**
     * Creates an empty {@code ObjectCountLinkedHashMap} instance.
     */
    static <K extends @Nullable Object> ObjectCountLinkedHashMap<K> create()
    {
        return new ObjectCountLinkedHashMap<K>();
    }

    /**
     * Creates a {@code ObjectCountLinkedHashMap} instance, with a high enough "initial capacity" that
     * it <i>should</i> hold {@code expectedSize} elements without growth.
     *
     * @param expectedSize the number of elements you expect to add to the returned set
     * @return a new, empty {@code ObjectCountLinkedHashMap} with enough capacity to hold {@code
     * expectedSize} elements without resizing
     * @throws IllegalArgumentException if {@code expectedSize} is negative
     */
    static <K extends @Nullable Object> ObjectCountLinkedHashMap<K> createWithExpectedSize(
            int expectedSize)
    {
        return new ObjectCountLinkedHashMap<K>(expectedSize);
    }

    private static final int ENDPOINT = -2;

    /*
     * The links field is not initialized directly in the constructor, but it's initialized by init(),
     * which the superconstructor calls.
     */

    /**
     * Contains the link pointers corresponding with the entries, in the range of [0, size()). The
     * high 32 bits of each long is the "prev" pointer, whereas the low 32 bits is the "succ" pointer
     * (pointing to the nextEntry entry in the linked list). The pointers in [size(), entries.length)
     * are all "null" (UNSET).
     *
     * <p>A node with "prev" pointer equal to {@code ENDPOINT} is the first node in the linked list,
     * and a node with "nextEntry" pointer equal to {@code ENDPOINT} is the last node.
     */
    @VisibleForTesting
    transient long[] links;

    /**
     * Pointer to the first node in the linked list, or {@code ENDPOINT} if there are no entries.
     */
    private transient int firstEntry;

    /**
     * Pointer to the last node in the linked list, or {@code ENDPOINT} if there are no entries.
     */
    private transient int lastEntry;

    ObjectCountLinkedHashMap()
    {
        this(DEFAULT_SIZE);
    }

    ObjectCountLinkedHashMap(int expectedSize)
    {
        this(expectedSize, DEFAULT_LOAD_FACTOR);
    }

    ObjectCountLinkedHashMap(int expectedSize, float loadFactor)
    {
        super(expectedSize, loadFactor);
    }

    ObjectCountLinkedHashMap(ObjectCountHashMap<K> map)
    {
        init(map.size(), DEFAULT_LOAD_FACTOR);
        for (int i = map.firstIndex(); i != -1; i = map.nextIndex(i))
        {
            put(map.getKey(i), map.getValue(i));
        }
    }

    @Override
    void init(int expectedSize, float loadFactor)
    {
        super.init(expectedSize, loadFactor);
        firstEntry = ENDPOINT;
        lastEntry = ENDPOINT;
        links = new long[expectedSize];
        Arrays.fill(links, UNSET);
    }

    @Override
    int firstIndex()
    {
        return (firstEntry == ENDPOINT) ? -1 : firstEntry;
    }

    @Override
    int nextIndex(int index)
    {
        int result = getSuccessor(index);
        return (result == ENDPOINT) ? -1 : result;
    }

    @Override
    int nextIndexAfterRemove(int oldNextIndex, int removedIndex)
    {
        return (oldNextIndex == size()) ? removedIndex : oldNextIndex;
    }

    private int getPredecessor(int entry)
    {
        return (int) (links[entry] >>> 32);
    }

    private int getSuccessor(int entry)
    {
        return (int) links[entry];
    }

    private void setSuccessor(int entry, int succ)
    {
        long succMask = (~0L) >>> 32;
        links[entry] = (links[entry] & ~succMask) | (succ & succMask);
    }

    private void setPredecessor(int entry, int pred)
    {
        long predMask = (~0L) << 32;
        links[entry] = (links[entry] & ~predMask) | ((long) pred << 32);
    }

    private void setSucceeds(int pred, int succ)
    {
        if (pred == ENDPOINT)
        {
            firstEntry = succ;
        }
        else
        {
            setSuccessor(pred, succ);
        }
        if (succ == ENDPOINT)
        {
            lastEntry = pred;
        }
        else
        {
            setPredecessor(succ, pred);
        }
    }

    @Override
    void insertEntry(int entryIndex, @ParametricNullness K key, int value, int hash)
    {
        super.insertEntry(entryIndex, key, value, hash);
        setSucceeds(lastEntry, entryIndex);
        setSucceeds(entryIndex, ENDPOINT);
    }

    @Override
    void moveLastEntry(int dstIndex)
    {
        int srcIndex = size() - 1;
        setSucceeds(getPredecessor(dstIndex), getSuccessor(dstIndex));
        if (dstIndex < srcIndex)
        {
            setSucceeds(getPredecessor(srcIndex), dstIndex);
            setSucceeds(dstIndex, getSuccessor(srcIndex));
        }
        super.moveLastEntry(dstIndex);
    }

    @Override
    void resizeEntries(int newCapacity)
    {
        super.resizeEntries(newCapacity);
        int oldCapacity = links.length;
        links = Arrays.copyOf(links, newCapacity);
        Arrays.fill(links, oldCapacity, newCapacity, UNSET);
    }

    @Override
    public void clear()
    {
        super.clear();
        this.firstEntry = ENDPOINT;
        this.lastEntry = ENDPOINT;
    }
}
